Auflistung nach Schlagwort "Formal logic"

Sortiert nach: Sortierung: Ergebnisse:

  • Axiomatizations for propositional and modal team logic 
    Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2016)
    A framework is developed that extends Hilbert-style proof systems for propositional and modal logics to comprehend their team-based counterparts. The method is applied to classical propositional logic and the modal logic ...
  • Axiomatizing propositional dependence logics 
    Sano, Katsuhiko; Virtema, Jonni (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    We give sound and complete Hilbert-style axiomatizations for propositional dependence logic (PD), modal dependence logic (MDL), and extended modal dependence logic (EMDL) by extending existing axiomatizations for propositional ...
  • Backdoors for linear temporal logic 
    Meier, Arne; Ordyniak, Sebastian; Sridharan, Ramanujan; Schindler, Irena (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized ...
  • Decidability of predicate logics with team semantics 
    Kontinen, Juha; Kuusisto, Antti; Virtema, Jonni (Saarbrücken : Dagstuhl Publishing, 2016)
    We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIMEcomplete. Furthermore, we show that the ...
  • Dependence logic with a majority quantifier 
    Durand, Arnaud; Ebbing, Johannes; Kontinen, Juha; Vollmer, Heribert (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2011)
    We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers ...
  • On quantified propositional logics and the exponential time hierarchy 
    Hannula, Miika; Kontinen, Juha; Lück, Martin; Virtema, Jonni (Waterloo, NSW : Open Publishing Association, 2016)
    We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified ...
  • On the implicit graph conjecture 
    Chandoo, Maurice (Saarbrücken : Dagstuhl Publishing, 2016)
    The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomial-time computable label decoder. We approach this conjecture by investigating classes of label ...
  • Parametrised complexity of satisfiability in temporal logic 
    Lück, Martin; Meier, Arne; Schindler, Irena (Association for Computing Machinery, 2017)
    We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and ...
  • A van Benthem theorem for modal team semantics 
    Kontinen, Juha; Müller, Julian-Steffen; Schnoor, Henning; Vollmer, Heribert (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework ...